package vip.zhenzicheng.algorithm.sort;

import static vip.zhenzicheng.algorithm.util.ArrayUtils.swap;

/**
 * 快速排序
 *
 * @author zhenzicheng
 * @date 2022-06-20 12:42
 */
public class FastSort {

  public static void fastSort(int[] arr, int L, int R) {
    int index = partition(arr, L, R); // 分区位置
    if (index > L) {
      fastSort(arr, L, index - 1); // 重排左区间
    }
    if (index < R) {
      fastSort(arr, index + 1, R); // 重排右区间
    }
  }

  /*基于分区的快排*/
  public static int partition(int[] arr, int L, int R) {
    if (L == R) {
      return L;
    }
    int pivot = (int) (L + Math.random() * (R - L + 1)); // 选定一个基准数索引，一定落在[L,R]区间
    int zoneIndex = L - 1; // 默认分区索引在L的左边

    swap(arr, pivot, R); // 先将基准数对应元素与最后一个数交换，方便以后每次比较
    for (int i = L; i <= R; i++) {
      if (arr[i] <= arr[R]) { // 比基准数小时
        zoneIndex++; // 分区索引+1
        if (i > zoneIndex) { // 相当于如果之前存在着比基准数大的数会进入这个循环
          swap(arr, i, zoneIndex);
        }
      }
    }
    return zoneIndex; // 这样分区的数结果相对平均
  }
}
